/*!
 * \file bitmap.h
 *
 * \date Sep 24, 2013
 * \author Ricardo C. Corrêa (correa@lia.ufc.br)
 *
 * \brief Macros and inline functions for bitwise operations on bitmaps using bit-parallelism.
 *
 * A bitmap is an array of bits to represent sets in which a bit of index \c i represents element \c i of the set. For a bitmap \c B,
 * \c B[\c i] \c = \c 1 means that element \c i is in the set; otherwise, \c i is not.
 *
 * Bitmaps are defined as arrays of three different types depending on the number of bits per node, namely: \c unsigned \c char (8 bits
 * per node), \c unsigned \c long \c int (32 bits per node), and \c unsigned \c long \c long \c int (64 bits per node). The type
 * currently in use is selected by means of the definition of a macro name, respectively with \c -D_ARCH8_, \c -D_ARCH32_, or
 * \c -D_ARCH64_, in the \c gcc command line.
 */

#ifndef BITMAP_H_
#define BITMAP_H_

#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>

#ifdef _ARCH128_
#include <smmintrin.h> // SSE4

typedef union {
    __m128i m;
    unsigned long long int ui64[2];
} NODETYPE; //!< bitmap node's type

#define BSIZE 128
#define WSIZE 16
#define LOGB 7LL
#define LOGW 4
#define LOGBW 11

#define ONE 1LL
#define NODEMAX 0xFFFFFFFFFFFFFFFF
#define MASKB 0x7FLL
//#define MASKB 0xFFFFFFFFFFFFFFC0

#define MASKSZ 65
static const unsigned long long __mask[MASKSZ] = {
	0xFFFFFFFFFFFFFFFF,
	0xFFFFFFFFFFFFFFFE, 0xFFFFFFFFFFFFFFFC, 0xFFFFFFFFFFFFFFF8, 0xFFFFFFFFFFFFFFF0,
	0xFFFFFFFFFFFFFFE0, 0xFFFFFFFFFFFFFFC0, 0xFFFFFFFFFFFFFF80, 0xFFFFFFFFFFFFFF00,
	0xFFFFFFFFFFFFFE00, 0xFFFFFFFFFFFFFC00, 0xFFFFFFFFFFFFF800, 0xFFFFFFFFFFFFF000,
	0xFFFFFFFFFFFFE000, 0xFFFFFFFFFFFFC000, 0xFFFFFFFFFFFF8000, 0xFFFFFFFFFFFF0000,
	0xFFFFFFFFFFFE0000, 0xFFFFFFFFFFFC0000, 0xFFFFFFFFFFF80000, 0xFFFFFFFFFFF00000,
	0xFFFFFFFFFFE00000, 0xFFFFFFFFFFC00000, 0xFFFFFFFFFF800000, 0xFFFFFFFFFF000000,
	0xFFFFFFFFFE000000, 0xFFFFFFFFFC000000, 0xFFFFFFFFF8000000, 0xFFFFFFFFF0000000,
	0xFFFFFFFFE0000000, 0xFFFFFFFFC0000000, 0xFFFFFFFF80000000, 0xFFFFFFFF00000000,
	0xFFFFFFFE00000000, 0xFFFFFFFC00000000, 0xFFFFFFF800000000, 0xFFFFFFF000000000,
	0xFFFFFFE000000000, 0xFFFFFFC000000000, 0xFFFFFF8000000000, 0xFFFFFF0000000000,
	0xFFFFFE0000000000, 0xFFFFFC0000000000, 0xFFFFF80000000000, 0xFFFFF00000000000,
	0xFFFFE00000000000, 0xFFFFC00000000000, 0xFFFF800000000000, 0xFFFF000000000000,
	0xFFFE000000000000, 0xFFFC000000000000, 0xFFF8000000000000, 0xFFF0000000000000,
	0xFFE0000000000000, 0xFFC0000000000000, 0xFF80000000000000, 0xFF00000000000000,
	0xFE00000000000000, 0xFC00000000000000, 0xF800000000000000, 0xF000000000000000,
	0xE000000000000000, 0xC000000000000000, 0x8000000000000000, 0x0000000000000000
};

/*
 * Returns the number of 1-bits in x.
 */
static inline int __builtin_popcountsse(NODETYPE x) {
	return __builtin_popcountll(x.ui64[0]) + __builtin_popcountll(x.ui64[1]);
}

/*
 * Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
 */
static inline int __builtin_ffssse(NODETYPE x) {
	if (x.ui64[0] != 0)
		return __builtin_ffsll(x.ui64[0]);
	if (x.ui64[1] != 0)
		return __builtin_ffsll(x.ui64[1]) + 64;
	return 0;
}

/*
 * Returns one plus the index of the significant 1-bit of x next to i, or if x is zero, returns zero.
 */
static inline int __builtin_nextffssse(NODETYPE x, int i) {
	unsigned long long int masked;
	if (i < 63)
	{
		masked = x.ui64[0] & __mask[i + 1];
		if (masked != 0)
			return __builtin_ffsll(masked);
		i = 63;
	}
	masked = x.ui64[1] & __mask[i - 63];
	if (masked == 0)
		return 0;
	return __builtin_ffsll(masked) + 64;
}

/*
 * Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
 */
static inline int __builtin_clzsse(NODETYPE x) {
	if (x.ui64[1] != 0)
		return __builtin_clzll(x.ui64[1]);
	return __builtin_clzll(x.ui64[0]) + 64;
}

/*
 * Returns the number of leading 0-bits in x, starting at ith-bit position. If x is 0, the result is BSIZE.
 */
static inline int __builtin_prevclzsse(NODETYPE x, int i) {
	unsigned long long int masked;
	if (i > 64)
	{
		masked = x.ui64[1] & ~__mask[i - 64];
		if (masked != 0)
			return __builtin_clzll(masked);
		i = 64;
	}
	masked = x.ui64[0] & ~__mask[i];
	if (masked == 0)
		return BSIZE;
	return __builtin_clzll(masked) + 64;
}

#define NODECOUNTER(i) __builtin_popcountsse(i)
#define NODELEAST(w) (__builtin_ffssse(w)-1)
#define NODENEXTLEAST(w, i) (__builtin_nextffssse((w), (i))-1)
#define NODEMOST(i) (BSIZE-__builtin_clzsse(i)-1)
#define NODEPREVMOST(w, i) (BSIZE-__builtin_prevclzsse((w), (i))-1)
#define NODEISEMPTY(w) ((w).ui64[0] == 0 && (w).ui64[1] == 0)
#define NODEISNOTEMPTY(w) ((w).ui64[0] != 0 || (w).ui64[1] != 0)

#elif _ARCH32_  // see comments at #ifdef _ARCH8_
typedef unsigned long int NODETYPE; //!< Bitmap node's type
#define BSIZE 32					//!< Number of bits in a node
#define WSIZE 4						//!< Number of bytes in a node
#define LOGB 5L						//!< Logarithmic of BSIZE
#define LOGW 2L						//!< Logarithmic of WSIZE
#define LOGBW 7L					//!< LOGB \c + LOGW
#define ONE 1L						//!< Node set to \c 1
#define NODEMAX 0xFFFFFFFF			//!< Node's maximum value
#define MASKB 0x1FL					//!< Mask used to select the LOGB least significant bits
//#define MASKB 0xFFFFFFE0

#define MASKSZ 33					//!< Number of elements in __mask
static const NODETYPE __mask[MASKSZ] = {
	0xFFFFFFFF,
	0xFFFFFFFE, 0xFFFFFFFC, 0xFFFFFFF8, 0xFFFFFFF0,
	0xFFFFFFE0, 0xFFFFFFC0, 0xFFFFFF80, 0xFFFFFF00,
	0xFFFFFE00, 0xFFFFFC00, 0xFFFFF800, 0xFFFFF000,
	0xFFFFE000, 0xFFFFC000, 0xFFFF8000, 0xFFFF0000,
	0xFFFE0000, 0xFFFC0000, 0xFFF80000, 0xFFF00000,
	0xFFE00000, 0xFFC00000, 0xFF800000, 0xFF000000,
	0xFE000000, 0xFC000000, 0xF8000000, 0xF0000000,
	0xE0000000, 0xC0000000, 0x80000000, 0x00000000
};

static inline int nodeMost(NODETYPE i) {
	return (i) == 0 ? -1 : BSIZE-__builtin_clzl(i)-1;
}

#define NODECOUNTER(i) __builtin_popcountl(i)
#define NODELEAST(w) (__builtin_ffsl(w)-1)
#define NODENEXTLEAST(w, i) (NODELEAST((w) & __mask[i + 1]))
#define NODEMOST(i) (nodeMost(i))
#define NODEPREVMOST(w, i) (NODEMOST((w) & ~__mask[i]))
#define NODEISEMPTY(w) (w == 0)
#define NODEISNOTEMPTY(w) (w != 0)

#elif _ARCH64_

typedef unsigned long long int NODETYPE; //!< bitmap node's type
#define BSIZE 64
#define WSIZE 8
#define LOGB 6LL
#define LOGW 3
#define LOGBW 9

#define ONE 1LL
#define NODEMAX 0xFFFFFFFFFFFFFFFF
#define MASKB 0x3FLL
//#define MASKB 0xFFFFFFFFFFFFFFC0

#define MASKSZ 65
static const NODETYPE __mask[MASKSZ] = {
	0xFFFFFFFFFFFFFFFF,
	0xFFFFFFFFFFFFFFFE, 0xFFFFFFFFFFFFFFFC, 0xFFFFFFFFFFFFFFF8, 0xFFFFFFFFFFFFFFF0,
	0xFFFFFFFFFFFFFFE0, 0xFFFFFFFFFFFFFFC0, 0xFFFFFFFFFFFFFF80, 0xFFFFFFFFFFFFFF00,
	0xFFFFFFFFFFFFFE00, 0xFFFFFFFFFFFFFC00, 0xFFFFFFFFFFFFF800, 0xFFFFFFFFFFFFF000,
	0xFFFFFFFFFFFFE000, 0xFFFFFFFFFFFFC000, 0xFFFFFFFFFFFF8000, 0xFFFFFFFFFFFF0000,
	0xFFFFFFFFFFFE0000, 0xFFFFFFFFFFFC0000, 0xFFFFFFFFFFF80000, 0xFFFFFFFFFFF00000,
	0xFFFFFFFFFFE00000, 0xFFFFFFFFFFC00000, 0xFFFFFFFFFF800000, 0xFFFFFFFFFF000000,
	0xFFFFFFFFFE000000, 0xFFFFFFFFFC000000, 0xFFFFFFFFF8000000, 0xFFFFFFFFF0000000,
	0xFFFFFFFFE0000000, 0xFFFFFFFFC0000000, 0xFFFFFFFF80000000, 0xFFFFFFFF00000000,
	0xFFFFFFFE00000000, 0xFFFFFFFC00000000, 0xFFFFFFF800000000, 0xFFFFFFF000000000,
	0xFFFFFFE000000000, 0xFFFFFFC000000000, 0xFFFFFF8000000000, 0xFFFFFF0000000000,
	0xFFFFFE0000000000, 0xFFFFFC0000000000, 0xFFFFF80000000000, 0xFFFFF00000000000,
	0xFFFFE00000000000, 0xFFFFC00000000000, 0xFFFF800000000000, 0xFFFF000000000000,
	0xFFFE000000000000, 0xFFFC000000000000, 0xFFF8000000000000, 0xFFF0000000000000,
	0xFFE0000000000000, 0xFFC0000000000000, 0xFF80000000000000, 0xFF00000000000000,
	0xFE00000000000000, 0xFC00000000000000, 0xF800000000000000, 0xF000000000000000,
	0xE000000000000000, 0xC000000000000000, 0x8000000000000000, 0x0000000000000000
};

static inline int nodeMost(NODETYPE i) {
	return (i) == 0 ? -1 : BSIZE-__builtin_clzll(i)-1;
}

#define NODECOUNTER(i) __builtin_popcountll(i)
#define NODELEAST(w) (__builtin_ffsll(w)-1)
#define NODENEXTLEAST(w, i) (NODELEAST((w) & __mask[i + 1]))
#define NODEMOST(i) (nodeMost(i))
#define NODEPREVMOST(w, i) (NODEMOST((w) & ~__mask[i]))
#define NODEISEMPTY(w) (w == 0)
#define NODEISNOTEMPTY(w) (w != 0)

#else
/*! \typedef NODETYPE
 * \brief Bitmap node's type
 *
 */
typedef unsigned char NODETYPE; 			//!< Bitmap node's type
#define BSIZE 8								//!< Number of bits in a node
#define WSIZE 1								//!< Number of bytes in a node
#define LOGB 3								//!< Logarithmic of BSIZE
#define LOGW 0								//!< Logarithmic of WSIZE
#define LOGBW 3								//!< LOGB \c + LOGW
#define ONE 1								//!< Node set to \c 1
#define NODEMAX 0xFF						//!< Node's maximum value
#define MASKB 0x07							//!< Mask used to select the LOGB least significant bits
//#define MASKB 0xFFFFFFE0

#define MASKSZ 9							//!< Number of elements in __mask
static const NODETYPE __mask[MASKSZ] = { //!< Array of masks. Entry \c i deletes the \c i least significant bits.
		0xFF, 0xFE, 0xFC, 0xF8, 0xF0, 0xE0, 0xC0, 0x80, 0x00 };

static inline int nodeMost(NODETYPE i) {
	return (i) == 0 ? -1 : BSIZE-__builtin_clz(i)-1;
}

#define NODECOUNTER(w) __builtin_popcount(w)						//!< Builtin function: Returns the number of 1-bits in \c w.
#define NODELEAST(w) (__builtin_ffs(w)-1)							//!< Builtin function: Returns the index of the least significant 1-bit of \c w, or if \c w is zero, returns \c -1.
#define NODENEXTLEAST(w, i) (NODELEAST((w) & __mask[i + 1]))		//!< Builtin function: Returns the index of the least significant 1-bit of \c w greater than \c i, or if \c w is zero, returns \c -1.
#define NODEMOST(i) (nodeMost(i))									//!< Builtin function: Returns the index of the most significant 1-bit of \c w, or if \c w is zero, returns \c -1.
#define NODEPREVMOST(w, i) (NODEMOST((w) & ~__mask[i]))				//!< Builtin function: Returns the index of the most significant 1-bit of \c w smaller than \c i, or if \c w is zero, returns \c -1.
#define NODEISEMPTY(w) (w == 0)
#define NODEISNOTEMPTY(w) (w != 0)
#endif

#define NELEM(i) ((i) << LOGB)										//!< Smallest element in the entry \c i of the bitmap.
#define NODEIDX(i) ((i) >> LOGB)									//!< Node index in the bitmap of element \c i.
#define IDXINNODE(i) ((i) & MASKB)									//!< Element index in the corresponding node of the bitmap.
#define ISINNODE(w, i) ((w) & (ONE << (i)))							//!< Returns a node set to a non-zero value if the bit of index \c i in node \c w is a 1-bit; otherwise a node set to \c 0.
#define RETAINLEAST(w, i) ((w) & (NODEMAX >> (BSIZE-(i)))) 			//!< Retains \c i least significant elements of node \c w.

typedef struct {
	int n;
	int nnodes;
	NODETYPE * minRNode; //<! a lower bound for the node index of the smallest element in the set
	NODETYPE * maxRNode; //<! an upper bound for the node index of the greatest element in the set
	NODETYPE * R;
} BitMap;

typedef struct {
	int ind;			//!< Node index in a bitmap.
	int nelem;			//!< Smallest element that can be in this node of a bitmap.
	int cur;			//!< Current element as an index in this node.
	NODETYPE * beg1;	//!< Used for backward enumeration
	NODETYPE * end1;	//!< Used for forward enumeration
	NODETYPE * buf1;	//!< Used to enumerate
} Node;

static void printNode(Node * node);
static void printSetNodes(BitMap const * s);

static inline BitMap *newBitMap(size_t n) {
	int tam = (NODEIDX(n-1)<<LOGW) + WSIZE + WSIZE + sizeof(char *);

	BitMap * ret = (BitMap *) malloc(sizeof(BitMap)+tam);
	char *ptr = (char *) ret + sizeof(BitMap);

	if (ptr==NULL)
		return(NULL);
	memset(ptr, 0, tam);

	ret->n = n;
	ret->nnodes = NODEIDX(n-1)+1;
	ret->R = (NODETYPE *) (ptr + sizeof(char *) + (WSIZE - (((intptr_t) (ptr + sizeof(char *))) & (WSIZE-1))));
	ret->minRNode = ret->R;
	ret->maxRNode = ret->minRNode+ret->nnodes;
	*(((char **) ret->R)-1) = (char *) ret;

	return ret;
}

static inline void freeBitMap(BitMap *ptr) {
	free(*(((char **) ptr->R)-1));
}

static inline BitMap *newBitMapVector(size_t size, size_t n) {
	int tam = ((NODEIDX(n-1)<<LOGW) + WSIZE)*size + WSIZE + sizeof(char *);

	BitMap * ret = (BitMap *) malloc(sizeof(BitMap)*size+tam);
	char *ptr = (char *) ret + sizeof(BitMap)*size;

	if (ptr==NULL)
		return(NULL);
	memset(ptr, 0, tam);

	tam = NODEIDX(n-1)+1;
	NODETYPE * R = (NODETYPE *) (ptr + sizeof(char *) + (WSIZE - (((intptr_t) (ptr + sizeof(char *))) & (WSIZE-1))));
	int i, q;
	for (i = 0, q = 0; i < size; i++, q += tam) {
		ret[i].n = n;
		ret[i].nnodes = NODEIDX(n-1)+1;
		ret[i].R = R + q;
		ret[i].minRNode = ret[i].R;
		ret[i].maxRNode = ret[i].minRNode+ret[i].nnodes;
	}

	*(((char **) R)-1) = (char *) ret;

	return ret;
}

// Deletes bit \c i from node \c w.
static inline void delElement(BitMap * bm, Node const * i) {
#if defined(_ARCH8_) || defined(_ARCH32_) || defined(_ARCH64_)
	*(bm->R+i->ind) &= ~(ONE << (i->cur));
#else
	if (i->cur < 64)
		(bm->R+i->ind)->ui64[0] &= ~(ONE << (i->cur));
	else
		(bm->R+i->ind)->ui64[1] &= ~(ONE << (i->cur-64));
#endif
}

// Adds bit \c i to node \c w.
static inline void addElement(BitMap * bm, Node const * i) {
#if defined(_ARCH8_) || defined(_ARCH32_) || defined(_ARCH64_)
	*(bm->R+i->ind) |= (ONE << (i->cur));
#else
	if (i->cur < 64)
		(bm->R+i->ind)->ui64[0] |= (ONE << (i->cur));
	else
		(bm->R+i->ind)->ui64[1] |= (ONE << (i->cur-64));
//	printf("add i=%d  nodeidx=%d  idx=%d  node0=%llx  node1=%llx\n",i->nelem+i->cur,i->ind,i->cur,(bm->R+i->ind)->ui64[0],(bm->R+i->ind)->ui64[1]);
#endif
}

// Inverts bit \c i to node \c w.
static inline void invElement(BitMap * bm, Node const * i) {
#if defined(_ARCH8_) || defined(_ARCH32_) || defined(_ARCH64_)
	*(bm->R+i->ind) ^= (ONE << (i->cur));
#else
	if (i->cur < 64)
		(bm->R+i->ind)->ui64[0] ^= (ONE << (i->cur));
	else
		(bm->R+i->ind)->ui64[1] ^= (ONE << (i->cur-64));
//	printf("add i=%d  nodeidx=%d  idx=%d  node0=%llx  node1=%llx\n",i->nelem+i->cur,i->ind,i->cur,(bm->R+i->ind)->ui64[0],(bm->R+i->ind)->ui64[1]);
#endif
}

//!< Returns a node set to a non-zero value if the element \c i is in the bitmap \c T; otherwise a node set to \c 0.
static inline int hasElement(BitMap const * bm, int i) {
#if defined(_ARCH8_) || defined(_ARCH32_) || defined(_ARCH64_)
	return ISINNODE(*(bm->R+NODEIDX(i)), IDXINNODE(i)) != 0;
#else
	int idx = IDXINNODE(i);
//	printf("has i=%d  nodeidx=%d  idx=%d  node0=%llx  node1=%llx\n",i,NODEIDX(i),idx,(bm->R+NODEIDX(i))->ui64[0],(bm->R+NODEIDX(i))->ui64[1]);
	if (idx < 64)
		return ISINNODE((bm->R+NODEIDX(i))->ui64[0], idx) != 0;
	return ISINNODE((bm->R+NODEIDX(i))->ui64[1], idx-64) != 0;
#endif
}

static inline int isEmpty(BitMap * mvec) {
	NODETYPE * node = mvec->minRNode;
	while (node < mvec->maxRNode)
	{
		if (NODEISNOTEMPTY(*node))
			return 0;
		node++;
	}
	return 1;
}

static inline int isNotEmpty(BitMap * mvec) {
	NODETYPE * node = mvec->minRNode;
	while (node < mvec->maxRNode)
	{
		if (NODEISNOTEMPTY(*node))
			return 1;
		node++;
	}
	return 0;
}

static inline void subMap(BitMap * bm, BitMap * r, int i, int n) {
	r->R = bm->R+NODEIDX(i);
	r->minRNode = r->R;
	r->n = n;
	r->nnodes = NODEIDX(n-1)+1;
	r->maxRNode = r->R+r->nnodes;
}

// forward enumeration

static inline void beginWhile(BitMap const * bm, Node * node) {
	node->ind = 0;
	node->nelem = 0;
	node->cur = -1;
	node->end1 = bm->maxRNode;
	node->buf1 = bm->R;
}

static inline void nextCommon(BitMap const * bm, Node * node) {
	NODETYPE * buf2 = bm->R+node->ind;
    NODETYPE buf;
#if defined(_ARCH8_) || defined(_ARCH32_) || defined(_ARCH64_)
    buf = *node->buf1 & *buf2;
    node->cur = NODENEXTLEAST(buf, node->cur);
    if (node->cur < 0 && ++node->buf1 < node->end1)
    {
        buf = *node->buf1 & *++buf2;
		node->ind++;
		node->nelem += BSIZE;
    	while (buf == 0 && ++node->buf1 < node->end1)
    	{
            buf = *node->buf1 & *++buf2;
    		node->ind++;
    		node->nelem += BSIZE;
    	}
    	node->cur = NODENEXTLEAST(buf, -1);
    }
#else
    _mm_store_si128 ((__m128i *) &buf, _mm_and_si128 (*((__m128i *) buf2), *((__m128i *) node->buf1)));
    node->cur = NODENEXTLEAST(buf, node->cur);
    if (node->cur < 0 && ++node->buf1 < node->end1)
    {
    	_mm_store_si128 ((__m128i *) &buf, _mm_and_si128 (*((__m128i *) ++buf2), *((__m128i *) node->buf1)));
		node->ind++;
		node->nelem += BSIZE;
    	while (buf.ui64[0] == 0 && buf.ui64[1] == 0 && ++node->buf1 < node->end1)
    	{
    		_mm_store_si128 ((__m128i *) &buf, _mm_and_si128 (*((__m128i *) ++buf2), *((__m128i *) node->buf1)));
    		node->ind++;
    		node->nelem += BSIZE;
    	}
    	node->cur = NODENEXTLEAST(buf, -1);
    }
#endif
}

static inline void beginCommon(BitMap const * abm, BitMap const * bm, Node * node) {
	beginWhile(bm, node);
	nextCommon(bm, node);
}

static inline void next(Node * node) {
	node->cur = NODENEXTLEAST(*node->buf1, node->cur);
	while (node->cur < 0 && ++node->buf1 < node->end1) {
		node->ind++;
		node->nelem += BSIZE;
		node->cur = NODENEXTLEAST(*node->buf1, -1);
	}
}

static inline void begin(BitMap const * bm, Node * node) {
	beginWhile(bm, node);
	next(node);
}

static inline int end(Node * node) {
	return node->buf1 >= node->end1;
}

static inline void copySets(Node * node, Node * anode) {
	int d = (anode->end1-anode->buf1);
	node->buf1 = node->end1-d;
	node->ind = anode->ind;
	node->nelem = anode->nelem;
	node->cur = anode->cur;
	memcpy(node->buf1, anode->buf1, d << LOGW);
}

// backward enumeration

static inline void rearWhile(BitMap const * bm, Node * node) {
	node->ind = bm->nnodes-1;
	node->nelem = NELEM(node->ind);
	node->cur = BSIZE;
	node->beg1 = bm->minRNode-1;
	node->buf1 = bm->maxRNode-1;
}

static inline void prevCommon(BitMap const * bm, Node * node) {
	NODETYPE * buf2 = bm->R+node->ind;
    NODETYPE buf;
#if defined(_ARCH8_) || defined(_ARCH32_) || defined(_ARCH64_)
    buf = *node->buf1 & *buf2;
    node->cur = NODEPREVMOST(buf, node->cur);
    if (node->cur < 0 && --node->buf1 > node->beg1)
    {
        buf = *node->buf1 & *--buf2;
		node->ind--;
		node->nelem -= BSIZE;
    	while (buf == 0 && --node->buf1 > node->beg1)
    	{
            buf = *node->buf1 & *--buf2;
    		node->ind--;
    		node->nelem -= BSIZE;
    	}
    	node->cur = NODEPREVMOST(buf, BSIZE);
    }
#else
    _mm_store_si128 ((__m128i *) &buf, _mm_and_si128 (*((__m128i *) buf2), *((__m128i *) node->buf1)));
    node->cur = NODEPREVMOST(buf, node->cur);
    if (node->cur < 0 && --node->buf1 > node->beg1)
    {
    	_mm_store_si128 ((__m128i *) &buf, _mm_and_si128 (*((__m128i *) --buf2), *((__m128i *) node->buf1)));
		node->ind--;
		node->nelem -= BSIZE;
    	while (buf.ui64[0] == 0 && buf.ui64[1] == 0 && --node->buf1 > node->beg1)
    	{
    		_mm_store_si128 ((__m128i *) &buf, _mm_and_si128 (*((__m128i *) --buf2), *((__m128i *) node->buf1)));
    		node->ind--;
    		node->nelem -= BSIZE;
    	}
    	node->cur = NODEPREVMOST(buf, BSIZE);
    }
#endif
}

static inline void rearCommon(BitMap const * abm, BitMap const * bm, Node * node) {
	rearWhile(bm, node);
	prevCommon(bm, node);
}

static inline void prev(Node * node) {
	node->cur = NODEPREVMOST(*node->buf1, node->cur);
	while (node->cur < 0 && --node->buf1 > node->beg1) {
		node->ind--;
		node->nelem -= BSIZE;
		node->cur = NODEPREVMOST(*node->buf1, BSIZE);
	}
}

static inline void rear(BitMap const * bm, Node * node) {
	rearWhile(bm, node);
	prev(node);
}

static inline int head(Node * node) {
	return node->buf1 <= node->beg1;
}

static inline void getNode(Node * node, int i) {
	node->ind = NODEIDX(i);
	node->nelem = NELEM(node->ind);
	node->cur = IDXINNODE(i);
}

static inline void printNode(Node * node) {
	printf("ind=%d  nelem=%d  cur=%d  elem=%d\n",node->ind,	node->nelem, node->cur, node->nelem+ node->cur);
}

static inline int getElement(Node const * node) {
	return node->nelem + node->cur;
}

static inline void setElement(Node * node, int i) {
	node->ind = NODEIDX(i);
	node->nelem = NELEM(i);
	node->cur = IDXINNODE(i);
}

/*!
 * \fn int cardOfSet(BitMap * bmvec)
 * \brief Determines the number of elements in the specified nodes of a bitmap.
 *
 * \param bmvec Bitmap.
 *
 * \return The number of elements in the nodes of the bitmap \c bmvec.
 */
static inline int cardOfSet(BitMap const * bmvec) {
	int ret = 0;
	NODETYPE * node;
	for (node = bmvec->minRNode; node < bmvec->maxRNode; node++)
		ret += NODECOUNTER(*node);
	return ret;
}

/*!
 * \fn void copyAll(BitMap * bmvec, BitMap * abmvec)
 * \brief Copy nodes between specified bitmaps.
 *
 * \param bmvec Nodes are copied to this bitmap.
 * \param abmvec Nodes are copied from this bitmap.
 */
static inline void copyAll(BitMap * bmvec, BitMap const * abmvec) {
	memcpy(bmvec->minRNode, abmvec->minRNode, abmvec->nnodes << LOGW);
}

/*!
 * \fn void addAll(BitMap * bmvec, BitMap * abmvec)
 * \brief Add elements between specified bitmaps.
 *
 * This function performs a logic \c OR operation of the specified nodes.
 *
 * \param bmvec Elements are added to this bitmap.
 * \param abmvec Elements of this bitmap are added.
 */
static inline void addAll(BitMap * bmvec, BitMap const * abmvec) {
	NODETYPE * bnode;
	NODETYPE * abnode;

#if defined(_ARCH8_) || defined(_ARCH32_) || defined(_ARCH64_)
	for (bnode = bmvec->R, abnode = abmvec->minRNode; abnode < abmvec->maxRNode; bnode++, abnode++)
		*bnode |= *abnode;
#else
	for (bnode = bmvec->R, abnode = abmvec->minRNode; abnode < abmvec->maxRNode; bnode++, abnode++)
		_mm_store_si128 ((__m128i *) bnode, _mm_or_si128 (*((__m128i *) bnode), *((__m128i *) abnode)));
#endif
}

static inline void addAllElements(BitMap * bm) {
	memset(bm->R, 0xFF, (bm->nnodes << LOGW));
	bm->maxRNode--;

#if defined(_ARCH8_) || defined(_ARCH32_) || defined(_ARCH64_)
	*bm->maxRNode = RETAINLEAST(*bm->maxRNode,IDXINNODE(bm->n-1)+1);
#else
	if (IDXINNODE(bm->n-1) < 64)
	{
		bm->maxRNode->ui64[0] = RETAINLEAST(bm->maxRNode->ui64[0],IDXINNODE(bm->n-1)+1);
		bm->maxRNode->ui64[1] = 0;
	}
	else
		bm->maxRNode->ui64[1] = RETAINLEAST(bm->maxRNode->ui64[1],IDXINNODE(bm->n-1)+1);
#endif

	bm->maxRNode++;
}

//!< Deletes all elements from bitmap \c R.
static inline void delAllElements(BitMap * bm) {
	memset(bm->R, 0, (bm->nnodes << LOGW));
}

/*!
 * \fn void removeAll(BitMap * bmvec, BitMap * abmvec)
 * \brief Remove elements between specified bitmaps.
 *
 * This function performs a logic \c AND operation of the specified nodes from one bitmap with the negation of nodes from the other bitmap.
 *
 * \param bmvec Elements of this bitmap are removed.
 * \param abmvec Elements are removed from this bitmap.
 */
static inline void removeAll(BitMap * bmvec, BitMap const * rbmvec) {
	NODETYPE * bnode;
	NODETYPE * rbnode;

#if defined(_ARCH8_) || defined(_ARCH32_) || defined(_ARCH64_)
	for (bnode = bmvec->minRNode, rbnode = rbmvec->R; bnode < bmvec->maxRNode; bnode++, rbnode++)
		*bnode &= ~*rbnode;
#else
	for (bnode = bmvec->minRNode, rbnode = rbmvec->R; bnode < bmvec->maxRNode; bnode++, rbnode++)
		_mm_store_si128 ((__m128i *) bnode, _mm_andnot_si128 (*((__m128i *) rbnode), *((__m128i *) bnode)));
#endif
}

static inline void removeFrom(Node * node, BitMap const * rbmvec) {
	NODETYPE * bnode;
	NODETYPE * rbnode;

#if defined(_ARCH8_) || defined(_ARCH32_) || defined(_ARCH64_)
	for (bnode = node->buf1, rbnode = rbmvec->R+node->ind; bnode < node->end1; bnode++, rbnode++)
		*bnode &= ~*rbnode;
#else
	for (bnode = node->buf1, rbnode = rbmvec->R+node->ind; bnode < node->end1; bnode++, rbnode++)
		_mm_store_si128 ((__m128i *) bnode, _mm_andnot_si128 (*((__m128i *) rbnode), *((__m128i *) bnode)));
#endif
}

/*!
 * \fn void retainAll(BitMap * bmvec, BitMap * abmvec)
 * \brief Intersection of bitmaps with the result in one of them.
 *
 * This function performs a logic \c AND operation of the specified nodes.
 *
 * \param bmvec Elements of this bitmap are removed.
 * \param abmvec Elements are removed from this bitmap.
 */
static inline void retainAll(BitMap * bmvec, BitMap const * rbmvec) {
	NODETYPE * bnode;
	NODETYPE * rbnode;

#if defined(_ARCH8_) || defined(_ARCH32_) || defined(_ARCH64_)
	for (bnode = bmvec->minRNode, rbnode = rbmvec->R; bnode < bmvec->maxRNode; bnode++, rbnode++)
		*bnode &= *rbnode;
#else
	for (bnode = bmvec->minRNode, rbnode = rbmvec->R; bnode < bmvec->maxRNode; bnode++, rbnode++)
		_mm_store_si128 ((__m128i *) bnode, _mm_and_si128 (*((__m128i *) rbnode), *((__m128i *) bnode)));
#endif
}
static inline void retainFrom(BitMap * bmvec, BitMap const * rbmvec, Node * node) {
	NODETYPE * bnode;
	NODETYPE * rbnode;

#if defined(_ARCH8_) || defined(_ARCH32_) || defined(_ARCH64_)
	for (bnode = node->buf1, rbnode = rbmvec->R+node->ind; bnode < bmvec->maxRNode; bnode++, rbnode++)
		*bnode &= *rbnode;
#else
	for (bnode = node->buf1, rbnode = rbmvec->R+node->ind; bnode < bmvec->maxRNode; bnode++, rbnode++)
		_mm_store_si128 ((__m128i *) bnode, _mm_and_si128 (*((__m128i *) rbnode), *((__m128i *) bnode)));
#endif
}

static inline void symDiff(BitMap * bmvec, BitMap const * rbmvec) {
	NODETYPE * bnode;
	NODETYPE * rbnode;

#if defined(_ARCH8_) || defined(_ARCH32_) || defined(_ARCH64_)
	for (bnode = bmvec->minRNode, rbnode = rbmvec->R; bnode < bmvec->maxRNode; bnode++, rbnode++)
		*bnode ^= *rbnode;
#else
	for (bnode = bmvec->minRNode, rbnode = rbmvec->R; bnode < bmvec->maxRNode; bnode++, rbnode++)
		_mm_store_si128 ((__m128i *) bnode, _mm_xor_si128 (*((__m128i *) rbnode), *((__m128i *) bnode)));
#endif
}
static inline void symDiffFrom(BitMap * bmvec, BitMap const * rbmvec, Node * node) {
	NODETYPE * bnode;
	NODETYPE * rbnode;

#if defined(_ARCH8_) || defined(_ARCH32_) || defined(_ARCH64_)
	for (bnode = node->buf1, rbnode = rbmvec->R+node->ind; bnode < bmvec->maxRNode; bnode++, rbnode++)
		*bnode ^= *rbnode;
#else
	for (bnode = node->buf1, rbnode = rbmvec->R+node->ind; bnode < bmvec->maxRNode; bnode++, rbnode++)
		_mm_store_si128 ((__m128i *) bnode, _mm_xor_si128 (*((__m128i *) rbnode), *((__m128i *) bnode)));
#endif
}

/*!
 * \fn void intersectOf(BitMap * bmvec, BitMap * abmvec, BitMap * bbmvec)
 * \brief Intersection of bitmaps with the result in a third bitmap.
 *
 * This function performs a logic \c AND operation of the specified nodes.
 *
 * \param bmvec Result bitmap
 * \param abmvec Operand bitmap
 * \param bbmvec Operand bitmap
 */
static inline void intersectOf(BitMap * bmvec, BitMap const * abmvec, BitMap const * bbmvec) {
	NODETYPE * bnode;
	NODETYPE * abnode;
	NODETYPE * bbnode;

#if defined(_ARCH8_) || defined(_ARCH32_) || defined(_ARCH64_)
	for (bnode = bmvec->minRNode, abnode = abmvec->minRNode, bbnode = bbmvec->minRNode; bnode < bmvec->maxRNode; bnode++, abnode++, bbnode++)
		*bnode = *abnode & *bbnode;
#else
	for (bnode = bmvec->minRNode, abnode = abmvec->minRNode, bbnode = bbmvec->minRNode; bnode < bmvec->maxRNode; bnode++, abnode++, bbnode++)
		_mm_store_si128 ((__m128i *) bnode, _mm_and_si128 (*((__m128i *) abnode), *((__m128i *) bbnode)));
#endif
}

static inline void printSetNodes(BitMap const * s) {
	NODETYPE * node;

#ifdef _ARCH32_
#define FORMX " %lx"
#elif _ARCH64_
#define FORMX " %llx"
#elif _ARCH128_
#define FORMX " %llx %llx"
#else
#define FORMX " %x"
#endif

	printf("SET: [");
	for (node = s->R+NODEIDX(s->n-1); node >= s->R; node--)
#if defined(_ARCH8_) || defined(_ARCH32_) || defined(_ARCH64_)
		printf(FORMX, *node);
#else
		printf(FORMX, node->ui64[1], node->ui64[0]);
#endif
	printf(" ]\n");
}

#endif /* BITMAP_H_ */
